We first prove that Littlestone classes, those which model theorists call stable, characterize learnability in a new statistical model: a learner in this new setting outputs the same hypothesis, up to measure zero, with probability one, after a uniformly bounded number of revisions. This fills a certain gap in the literature, and sets the stage for an approximation theorem characterizing Littlestone classes in terms of a range of learning models, by analogy to definability of types in model theory. We then give a complete analogue of Shelah's celebrated (and perhaps a priori untranslatable) Unstable Formula Theorem in the learning setting, with algorithmic arguments taking the place of the infinite.

We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to the more general setting of density estimation (with respect to the total variation metric). The existence of a universally consistent DP learner reveals a stark difference with the distribution-free PAC model. Indeed, in the latter DP learning is extremely limited: even one-dimensional linear classifiers are not privately learnable in this stringent model. Our result thus demonstrates that by allowing the learning rate to depend on the target distribution, one can circumvent the above-mentioned impossibility result and in fact, learn \emph{arbitrary} distributions by a single DP algorithm. As an application, we prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal \emph{labeled} sample complexity of $\tilde{O}(d/\varepsilon)$ labeled examples (and with an unlabeled sample complexity that can depend on the target distribution).

学习曲线将学习算法的预期误差绘制为标记输入样本数量的函数。它们被机器学习实践者广泛使用，以衡量算法的性能，但是经典的PAC学习理论无法解释其行为。在本文中，我们介绍了一种称为VCL维度的新组合表征，该表征改进并完善了Bousquet等人的最新结果。 （2021）。我们的表征通过提供细粒度的边界来展示学习曲线的结构，并表明对于有限VCL的类，可以将衰减的速率分解为仅取决于假设类别和指数成分的线性组件，该成分是指数的成分。还取决于目标分布。特别是，VCL维度的细微差别意味着比Bousquet等人的边界更强大的下限。 （2021年），比经典的“无免费午餐”下界强。 VCL表征解决了Antos and Lugosi（1998）研究的一个开放问题，他们询问在哪些情况下存在这种下限。作为推论，我们在$ \ mathbb {r}^d $中恢复了其下限，并以原则性的方式也适用于其他情况。最后，为了对我们的工作以及与传统PAC学习界的比较提供另一个观点，我们还以一种更接近PAC环境的语言展示了结果的替代表述。

我们提出了Pac-Bayes风格的概括结合，该结合可以用各种积分概率指标（IPM）替换KL-Divergence。我们提供了这种结合的实例，IPM是总变异度量和Wasserstein距离。获得的边界的一个显着特征是，它们在最坏的情况下（当前和后距离彼此远距离时）在经典均匀收敛边界之间自然插值，并且在更好的情况下（后验和先验都关闭时）优选界限。这说明了使用算法和数据依赖性组件加强经典概括界限的可能性，从而使它们更适合分析使用大假设空间的算法。

我们研究了学习算法的输出及其$ n $培训数据之间（某些摘要）之间的共同信息，以$ n+1 $ i.i.d.的超级样本为条件。随机选择训练数据而无需更换的数据。这些算法（Steinke and Zakynthinou，2020）的条件相互信息（CMI）的这些剩余变体也被认为可以控制具有有界损耗函数的学习算法的平均通用误差。为了学习在0-1损失（即插值算法）下实现零经验风险的学习算法，我们提供了剩余的CMI与风险的经典保留误差估计之间的明确联系。使用此连接，我们就（评估）保留的CMI获得了上限和下限。当限制风险恒定或多项式衰减时，边界会收敛到两个恒定因子。作为应用程序，我们分析了单个包含图算法的人口风险，这是一种在可实现的环境中的VC类的通用转导学习算法。使用一对一的CMI，我们匹配在可实现的设置中学习VC课程的最佳界限，回答了Steinke和Zakynthinou（2020）提出的开放挑战。最后，为了理解剩余的CMI在研究概括中的作用，我们将剩余的CMI放在措施层次结构中，并在根本上使用新颖的无条件相互信息。对于0-1的损失和插值学习算法，观察到此相互信息恰恰是风险。

考虑到数据在几个方之间分配的学习任务，沟通是当事方希望最大程度地减少的基本资源之一。我们提出了一种分布式增强算法，该算法具有有限的噪声。我们的算法类似于经典的增强算法，尽管它配备了一种新组件，灵感来自Impagliazzo的硬核Lemma \ cite {Impagliazzo1995hard}，并在算法中添加了健壮性质量。我们还通过证明对任何渐近上更大的噪声的弹性是无法通过沟通效率算法来实现的，从而补充了这一结果。

监督学习通常依赖于真实标签的手动注释。当有许多潜在的类别时，寻找最佳的班级对于人类注释者可能会过时。另一方面，比较两个候选标签通常要容易得多。我们专注于这种成对的监督，并询问如何有效地用于学习，尤其是在积极学习中。在这种情况下，我们获得了一些有见地的结果。原则上，可以使用$ K-1 $ Active查询来找到最好的$ K $标签。我们表明，有一种自然阶级，这种方法是最佳选择的，并且有更具比较的主动学习方案。我们分析中的一个关键要素是真实分布的“标签邻域图”，如果两个类共享决策边界，则在两个类之间具有优势。我们还表明，在PAC设置中，成对比较在最坏情况下不能提供改善的样品复杂性。我们通过实验补充了理论结果，清楚地证明了邻里图对样品复杂性的影响。

训练数据的量是决定学习算法的概括能力的关键因素之一。直观地，人们期望随着训练数据的增加，错误率将降低。也许令人惊讶的是，自然尝试正式化这种直觉引起了有趣且具有挑战性的数学问题。例如，在他们关于模式识别的古典书籍中，Devroye，Gyorfi和Lugosi（1996）询问是否存在{单调}贝叶斯一致的算法。这个问题一直开放25年以上，直到最近Pestov（2021）使用单调贝叶斯一致算法的复杂构造解决了该问题进行二进制分类。我们得出了多类分类的一般结果，表明每个学习算法A都可以转换为具有相似性能的单调。此外，转换是有效的，仅使用黑盒甲骨文访问A。 Loog（2019），Viering and Loog（2021）和Mhammedi（2021）。我们的转换很容易意味着在各种情况下单调学习者：例如，它将Pestov的结果扩展到具有任意数量的标签的分类任务。这与针对二进制分类量身定制的Pestov的工作形成鲜明对比。另外，我们在单调算法的误差上提供统一的边界。这使我们的转换适用于无分销设置。例如，在PAC学习中，这意味着每个可学习的课程都接受单调PAC学习者。这通过Viering，Mey和Loog（2019）解决了问题； Viering and Loog（2021）; Mhammedi（2021）。

我们研究了三个看似不同的组合结构之间的联系 - 在统计和概率理论中的“统一”括号，“在线和分布式学习理论”和“组合MacBeath地区”，或者在离散和计算几何中的MNET。我们表明这三个概念是单一组合物业的表现，可以在沿着VAPNIK-Chervonenkis型理论的统一框架中表达的统一收敛性。这些新连接有助于我们带来来自离散和计算几何的工具，以证明这些对象的改进界限。我们改进的界限有助于获得半个空间的分布式学习的最佳算法，一种改进的分布式凸起脱节问题，以及对大类半代数阈值函数的平滑对手的在线算法的改进的后悔界限。

在这项工作中，我们调查了Steinke和Zakynthinou（2020）的“条件互信息”（CMI）框架的表现力，以及使用它来提供统一框架，用于在可实现的环境中证明泛化界限。我们首先证明可以使用该框架来表达任何用于从一类界限VC维度输出假设的任何学习算法的非琐碎（但是次优）界限。我们证明了CMI框架在用于学习半个空间的预期风险上产生最佳限制。该结果是我们的一般结果的应用，显示稳定的压缩方案Bousquet al。 （2020）尺寸$ k $有统一有限的命令$ o（k）$。我们进一步表明，适当学习VC类的固有限制与恒定的CMI存在适当的学习者的存在，并且它意味着对Steinke和Zakynthinou（2020）的开放问题的负面分辨率。我们进一步研究了价值最低限度（ERMS）的CMI的级别$ H $，并表明，如果才能使用有界CMI输出所有一致的分类器（版本空间），只有在$ H $具有有界的星号（Hanneke和杨（2015）））。此外，我们证明了一般性的减少，表明“休假”分析通过CMI框架表示。作为推论，我们研究了Haussler等人提出的一包图算法的CMI。 （1994）。更一般地说，我们表明CMI框架是通用的，因为对于每一项一致的算法和数据分布，当且仅当其评估的CMI具有样品的载位增长时，预期的风险就会消失。